//https://leetcode.cn/problems/intersection-of-two-arrays-ii/
//看到这种和重复,两个数组有关的,都应该优先考虑HashSet!
package dataStructure.Test350两个数组的交集II;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        //首先要确保nums1的长度小于nums2的长度
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }

        Map<Integer, Integer> map = new HashMap<>();
        //遍历nums1放入map中
        //key:num value:count
        int count;
        for (int num : nums1) {
            count = map.getOrDefault(num, 0) + 1;
            map.put(num, count);
        }
        //再遍历nums2,如果其中有在map中的元素,则count--,并且将该元素放入res数组中
        //res数组的长度应该定义为短的那个数组的长度,此处为nums1
        int[] res = new int[nums1.length];
        int index = 0;//往res数组放元素的下标
        for (int num : nums2) {
            count = map.getOrDefault(num, 0);
            if (count > 0) {
                res[index++] = num;
                count--;
                if (count > 0) {
                    map.put(num, count);
                } else {
                    map.remove(num);
                }
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }
}
